package com.pw.study.leetcode;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Stream;

/**
 * @Desc: TODO
 * @author: future
 * @since: 2022/5/16-18:50
 */
public class $53_MaxArr {
    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int result = test(nums);
        test3(nums);
        System.out.println(result);

    }

    private static void test3(int[] nums) {

        for (int i =1; i <nums.length ; i++) {
            if(nums[i-1]>0){
                nums[i]=nums[i-1]+nums[i];
            }
            System.out.print(nums[i]+" ");
        }

        Arrays.sort(nums);
        System.out.println("num:"+nums[nums.length-1]);
    }

    private static void test2(int[] nums) {

        for (int i = 1; i < nums.length; i++) {
            if(nums[i-1]>0){
                nums[i]=+nums[i]+nums[i-1];
            }
        }
        Arrays.sort(nums);
        System.out.println(nums[nums.length-1]);



    }

    private static int test(int[] nums) {
        //贪心算法
        //当前值  之前和，当前和， 最大和
        int pre = nums[0],sum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            pre = Math.max(pre + nums[i], nums[i]);
            sum = Math.max(sum, pre);
        }
        return sum;
    }

}
